package week9.jsjf;

import weeek3.jsjf.LinkedQueue;
import weeek3.jsjf.QueueADT;
import week2.LinkedStack;
import week2.StackADT;
import week4.jsjf.ArrayUnorderedList;
import week4.jsjf.UnorderedListADT;

import java.util.ArrayList;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class ListCreation<T> implements GraphADT<T> {


         protected int numVertices;
        protected ArrayList<VertexNode> arrayList = new ArrayList<VertexNode>();
        protected T[] vertices;
        protected int modCount;

        public ListCreation(){
            numVertices = 0;
            modCount = 0;
        }


        @Override
        public void addVertex(T vertex) {
            VertexNode vertexNode = new VertexNode(vertex);
            arrayList.add(vertexNode);
            numVertices++;
            modCount++;
        }
        @Override
        public void addEdge(T vertex1, T vertex2) {
            if(getIndex(vertex1)!=-1&&getIndex(vertex2)!=-1){
                VertexNode<T> vertexNode1 = arrayList.get(getIndex(vertex1));
                VertexNode<T> vertexNode2 = arrayList.get(getIndex(vertex2));
                VertexNode<T> temp1 = new VertexNode<>(vertex1);
                VertexNode<T> temp2 = new VertexNode<>(vertex2);
                while(vertexNode1.getNext() !=null)
                    vertexNode1 = vertexNode1.getNext();
                vertexNode1.setNext(temp2);
                while(vertexNode2.getNext() !=null)
                    vertexNode2 = vertexNode2.getNext();
                vertexNode2.setNext(temp1);
            }
        }
        public void addEdge(int index1, int index2){
            addEdge(vertices[index1],vertices[index2]);
        }
        @Override
        public void removeVertex(T vertex) {
            VertexNode vertexNode = new VertexNode(vertex);
            arrayList.remove(vertexNode);
            numVertices--;
            modCount++;
        }
        public void removeVertex(int index){
            removeVertex(vertices[index]);
        }
        @Override
        public void removeEdge(T vertex1, T vertex2) {

            if(getIndex(vertex1)!=-1&&getIndex(vertex2)!=-1){
                VertexNode<T> vertexNode1 = arrayList.get(getIndex(vertex1));
                VertexNode<T> vertexNode2 = arrayList.get(getIndex(vertex2));
                VertexNode<T> temp1 = null,temp2 = null;

                while(vertexNode1.getElement() != vertex2 ) {
                    temp1 = vertexNode1;
                    vertexNode1 = vertexNode1.getNext();
                }
                if(vertexNode1.getNext()==null)
                    temp1.setNext(null);
                else{
                    VertexNode<T> temp = vertexNode1.getNext();
                    temp1.setNext(temp);
                }


                while(vertexNode2.getElement() != vertex1  ) {
                    temp2 = vertexNode2;
                    vertexNode2 = vertexNode2.getNext();
                }
                if(vertexNode2.getNext()==null)
                    temp2.setNext(null);
                else{
                    VertexNode<T> temp = vertexNode2.getNext();
                    temp2.setNext(temp);
                }
            }
        }
        public void removeEdge(int index1, int index2){
            removeEdge(vertices[index1],vertices[index2]);
        }
        public Iterator iteratorDFS(T startVertex) {
            return iteratorDFS(getIndex(startVertex));

        }
        public Iterator<T> iteratorDFS(int startIndex)
        {
            Integer x;
            boolean found;
            this.vertices = (T[])(new Object[numVertices]);
            StackADT<Integer> traversalStack = new LinkedStack<Integer>();
            UnorderedListADT<T> resultList = new ArrayUnorderedList<T>();
            boolean[] visited = new boolean[numVertices];

            if (!indexIsValid(startIndex))
                return resultList.iterator();

            for (int i = 0; i < numVertices; i++)
                visited[i] = false;

            traversalStack.push(startIndex);
            resultList.addToRear((T) arrayList.get(startIndex).getElement());
            visited[startIndex] = true;

            while (!traversalStack.isEmpty())
            {
                x = traversalStack.peek();
                found = false;

                //Find a vertex adjacent to x that has not been visited
                //     and push it on the stack
                for (int i = 0; (i < numVertices) && !found; i++)
                {
                    if (isEdge(x,i) && !visited[i])
                    {
                        traversalStack.push(i);
                        resultList.addToRear((T) arrayList.get(i).getElement());
                        visited[i] = true;
                        found = true;
                    }
                }
                if (!found && !traversalStack.isEmpty())
                    traversalStack.pop();
            }
            return new GraphIterator(resultList.iterator());
        }
        @Override
        public Iterator iteratorBFS(T startVertex) {
            return iteratorBFS(getIndex(startVertex));

        }
        public Iterator<T> iteratorBFS(int startIndex)
        {
            Integer x;
            QueueADT<Integer> traversalQueue = new LinkedQueue<Integer>();
            UnorderedListADT<T> resultList = new ArrayUnorderedList<T>();

            if (!indexIsValid(startIndex))
                return resultList.iterator();

            boolean[] visited = new boolean[numVertices];
            for (int i = 0; i < numVertices; i++)
                visited[i] = false;

            traversalQueue.enqueue(startIndex);
            visited[startIndex] = true;

            while (!traversalQueue.isEmpty())
            {
                x = traversalQueue.dequeue();
                resultList.addToRear((T) arrayList.get(x).getElement());

                //Find all vertices adjacent to x that have not been visited
                //     and queue them up

                for (int i = 0; i < numVertices; i++)
                {
                    if (isEdge(x,i) && !visited[i])
                    {
                        traversalQueue.enqueue(i);
                        visited[i] = true;
                    }

                }
            }
            return new GraphIterator(resultList.iterator());
        }
        protected boolean indexIsValid(int index)
        {
            if (index<numVertices)
                return true;
            else
                return false;
        }
        public boolean isEdge(int i, int j){
            if(i==j)
                return false;
            VertexNode vertexNode1 = arrayList.get(i);
            VertexNode vertexNode2 = arrayList.get(j);
            while(vertexNode1!=null) {
                if (vertexNode1.getElement() == vertexNode2.getElement())
                    return true;
                vertexNode1 =vertexNode1.getNext();
            }
            return false;
        }
        @Override
        public Iterator iteratorShortestPath(T startVertex, T targetVertex) {
            return iteratorShortestPath(getIndex(startVertex), getIndex(targetVertex));
        }
        public Iterator<T> iteratorShortestPath(int startIndex, int targetIndex)
        {
            UnorderedListADT<T> resultList = new ArrayUnorderedList<T>();
            if (!indexIsValid(startIndex) || !indexIsValid(targetIndex))
                return resultList.iterator();

            Iterator<Integer> it = iteratorShortestPathIndices(startIndex,
                    targetIndex);
            while (it.hasNext())
                resultList.addToRear((T) arrayList.get(((Integer)it.next())).getElement());
            return new GraphIterator(resultList.iterator());
        }
        protected Iterator<Integer> iteratorShortestPathIndices(int startIndex, int targetIndex)
        {
            int index = startIndex;
            int[] pathLength = new int[numVertices];
            int[] predecessor = new int[numVertices];
            QueueADT<Integer> traversalQueue = new LinkedQueue<Integer>();
            UnorderedListADT<Integer> resultList =
                    new ArrayUnorderedList<Integer>();

            if (!indexIsValid(startIndex) || !indexIsValid(targetIndex) ||
                    (startIndex == targetIndex))
                return resultList.iterator();

            boolean[] visited = new boolean[numVertices];
            for (int i = 0; i < numVertices; i++)
                visited[i] = false;

            traversalQueue.enqueue(Integer.valueOf(startIndex));
            visited[startIndex] = true;
            pathLength[startIndex] = 0;
            predecessor[startIndex] = -1;

            while (!traversalQueue.isEmpty() && (index != targetIndex))
            {
                index = (traversalQueue.dequeue()).intValue();

                //Update the pathLength for each unvisited vertex adjacent
                //     to the vertex at the current index.
                for (int i = 0; i < numVertices; i++)
                {
                    if (isEdge(index,i) && !visited[i])
                    {
                        pathLength[i] = pathLength[index] + 1;
                        predecessor[i] = index;
                        traversalQueue.enqueue(Integer.valueOf(i));
                        visited[i] = true;
                    }
                }
            }
            if (index != targetIndex)  // no path must have been found
                return resultList.iterator();

            StackADT<Integer> stack = new LinkedStack<Integer>();
            index = targetIndex;
            stack.push(Integer.valueOf(index));
            do
            {
                index = predecessor[index];
                stack.push(Integer.valueOf(index));
            } while (index != startIndex);

            while (!stack.isEmpty())
                resultList.addToRear(((Integer)stack.pop()));

            return new GraphIndexIterator(resultList.iterator());
        }
        public int shortestPathLength(int startIndex, int targetIndex)
        {
            int result = 0;
            if (!indexIsValid(startIndex) || !indexIsValid(targetIndex))
                return 0;

            int index1;
            Iterator<Integer> it = iteratorShortestPathIndices(startIndex,
                    targetIndex);

            if (it.hasNext())
                index1 = ((Integer)it.next()).intValue();
            else
                return 0;

            while (it.hasNext())
            {
                result++;
                it.next();
            }

            return result;
        }
        public int shortestPathLength(T startVertex, T targetVertex){
            return shortestPathLength(getIndex(startVertex),getIndex(targetVertex));
        }
        public int getIndex(T vertex){
            VertexNode vertexNode = new VertexNode(vertex);
            for(int i = 0;i<numVertices;i++){
                if(arrayList.get(i).getElement()==vertex)
                    return i;
            }
            return -1;
        }
        @Override
        public boolean isEmpty() {
            if(numVertices ==0)
                return true;
            else
                return false;
        }
        @Override
        public boolean isConnected() {
            boolean result = true;
            for(int i=0;i<numVertices;i++){
                int temp=0;
                temp=getSizeOfIterator(iteratorBFS(i));
                if(temp!=numVertices)
                {
                    result = false;
                    break;
                }
            }
            return result;
        }
        private int getSizeOfIterator(Iterator iterator) {
            int size = 0;
            while(iterator.hasNext()){
                size++;
                iterator.next();
            }
            return size;
        }
        @Override
        public int size() {
            return numVertices;
        }
        @Override
        public String toString(){
            if (numVertices == 0)
                return "Graph is empty";

            String result="顶点：";
            for (int i = 0; i < arrayList.size(); i++) {
                result += arrayList.get(i).getElement() + " ";
            }
            result += "\n\n边：\n";
            for (int i=0;i<numVertices;i++)
            {
                VertexNode<T> temp = arrayList.get(i);
                while(temp != null){
                    result += temp.getElement() + ",";
                    temp = temp.getNext();
                }
                result += "\n";
            }

            return result;
        }

        public class GraphIterator implements Iterator<T>
        {
            private int expectedModCount;
            private Iterator<T> iter;


            public GraphIterator(Iterator<T> iter)
            {
                this.iter = iter;
                expectedModCount = modCount;
            }



            @Override
            public boolean hasNext() throws ConcurrentModificationException
            {
                if (!(modCount == expectedModCount))
                    throw new ConcurrentModificationException();

                return (iter.hasNext());
            }


            @Override
            public T next() throws NoSuchElementException
            {
                if (hasNext())
                    return (iter.next());
                else
                    throw new NoSuchElementException();
            }


            @Override
            public void remove()
            {
                throw new UnsupportedOperationException();
            }
        }
        public class GraphIndexIterator implements Iterator<Integer>
        {
            private int expectedModCount;
            private Iterator<Integer> iter;


            public GraphIndexIterator(Iterator<Integer> iter)
            {
                this.iter = iter;
                expectedModCount = modCount;
            }


            @Override
            public boolean hasNext() throws ConcurrentModificationException
            {
                if (!(modCount == expectedModCount))
                    throw new ConcurrentModificationException();

                return (iter.hasNext());
            }


            @Override
            public Integer next() throws NoSuchElementException
            {
                if (hasNext())
                    return (iter.next());
                else
                    throw new NoSuchElementException();
            }


            @Override
            public void remove()
            {
                throw new UnsupportedOperationException();
            }
        }
    }


